package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/**
 * https://leetcode.cn/problems/univalued-binary-tree/description
 *
 * ```
 * 965. 单值二叉树
 * 如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
 * 只有给定的树是单值二叉树时，才返回 true；否则返回 false。
 *
 * 示例 1：
 * 输入：[1,1,1,1,1,null,1]
 * 输出：true
 *
 * 示例 2：
 * 输入：[2,2,2,5,2]
 * 输出：false
 *
 * 提示：
 * 给定树的节点数范围是 [1, 100]。
 * 每个节点的值都是整数，范围为 [0, 99] 。
 * ```
 */
class leetcode_965 {

    @Test
    fun test_1() {
        val n1_1 = TreeNode(1)
        val n1_2 = TreeNode(1)
        val n1_3 = TreeNode(1)
        val n1_4 = TreeNode(1)
        val n1_5 = TreeNode(1)
        val root = n1_1

        n1_1.left = n1_2
        n1_1.right = n1_2

        n1_2.left = n1_3
        n1_2.right = n1_4

        n1_3.right = n1_5

        val actual = isUnivalTree(root)
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val n2_1 = TreeNode(2)
        val n2_2 = TreeNode(2)
        val n2_3 = TreeNode(2)
        val n2_4 = TreeNode(2)
        val n5 = TreeNode(5)
        val root = n2_1

        n2_1.left = n2_2
        n2_1.right = n2_3

        n2_2.left = n5
        n2_2.right = n2_4

        val actual = isUnivalTree(root)
        val expected = false
        Assert.assertEquals(expected, actual)
    }

    private var n: Int = -1
    private fun isUnivalTree(root: TreeNode?): Boolean {
        /**
        题型：二叉树的任何一种递归方式都可以实现。代码中用的是前序遍历

        思路：
        保存root 节点，判断左右子树的节点是否与root节点的值相同。

        时间复杂度：O(N)，其中 N 是二叉树中的节点总数。

        空间复杂度：O(H)，其中 H 是二叉树的高度。
        递归实现的，所以空间复杂度主要来自于 递归调用栈。
        在递归过程中，函数调用会压入栈中。栈的最大深度取决于二叉树的 高度 (H)。
         */

        // 1 确定函数的参数以及返回值
        // 2 确定终止条件
        if (root == null) {  // root 为null时，符合
            return true
        }
        // 3 确定单层递归的处理逻辑：前序遍历
        // 中
        if (n == -1) {
            n = root.`val` // 保存root值
        } else {
            if (n != root.`val`) { // 判断节点是否与 root 值相同，若不同，则停止递归
                return false
            }
        }
        // 左
        val isLeft = isUnivalTree(root.left)
        if (!isLeft) { // 若左子树与root值不同，则停止递归
            return false
        }

        // 右
        val isRight = isUnivalTree(root.right)
        if (!isRight) { // 若右子树与root值不同，则停止递归
            return false
        }
        return true
    }

    fun isUnivalTree2(root: TreeNode?): Boolean {
        // 层级遍历
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if(null == root){
            return false
        }
        // 3 确定单次递归的处理逻辑：非递归，层级遍历
        val queue: LinkedList<TreeNode> =  LinkedList()
        queue.offer(root)

        while(!queue.isEmpty()){
            var size : Int = queue.size
            while(size -- > 0){
                val node = queue.poll()
                if(n != -1 && node.`val` != n){
                    return false
                }
                n = node.`val`
                node.left?.let{
                    queue.offer(it)
                }
                node.right?.let{
                    queue.offer(it)
                }
            }
        }
        return true
    }
}